package leetcode_600;

/**
 *@author 周杨
 *QuadTreeIntersection_558 四叉树交叉问题
 *describe:AC 81%
 *2018年9月14日 下午1:06:38
 */
public class QuadTreeIntersection_558 {
	
	class Node {
	    public boolean val;
	    public boolean isLeaf;
	    public Node topLeft;
	    public Node topRight;
	    public Node bottomLeft;
	    public Node bottomRight;

	    public Node() {}

	    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
	        val = _val;
	        isLeaf = _isLeaf;
	        topLeft = _topLeft;
	        topRight = _topRight;
	        bottomLeft = _bottomLeft;
	        bottomRight = _bottomRight;
	    }
	}
	
	 public Node intersect(Node quadTree1, Node quadTree2) {
	        return calc(quadTree1, quadTree2); 
	    }
	    
	    public Node calc (Node quadTree1, Node quadTree2) {
	        if (quadTree1.isLeaf==true) {
	            if (quadTree1.val==true) 
	                return new Node(true, true, null, null, null, null);
	            else 
	                return quadTree2; 
	        }
	        else if (quadTree2.isLeaf==true) {
	            if (quadTree2.val==true) 
	                return new Node(true, true, null, null, null, null);
	            else 
	                return quadTree1; 
	        }
	        else { 
	            Node res = new Node(); 
	            res.topLeft = calc(quadTree1.topLeft, quadTree2.topLeft);
	            res.topRight = calc(quadTree1.topRight, quadTree2.topRight);
	            res.bottomLeft = calc(quadTree1.bottomLeft, quadTree2.bottomLeft);
	            res.bottomRight = calc(quadTree1.bottomRight, quadTree2.bottomRight);
	            
	            if (res.topLeft.isLeaf==true && res.topLeft.val==true && res.topRight.isLeaf==true && res.topRight.val==true
	               && res.bottomLeft.isLeaf==true && res.bottomLeft.val==true && res.bottomRight.isLeaf==true && res.bottomRight.val==true) {
	                   res.isLeaf=true;
	                   res.val=true;
	            }
	            return res; 
	        }
	    }
}
